#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include "TestSortHelper.h"

using namespace std;
//https://www.cnblogs.com/protected/p/6603536.html
/**
 * 计数排序，通过数组记录对应的下标的数量。
 * @param arr
 * @param n
 */
void countSort(int  arr[], int n) {
    int max = -0x7fffffff;
    int min = 0x7fffffff;

    //找出数组中的最大最小值
    for (int i = 0; i < n; i++) {
        max = max>arr[i]?max:arr[i];
        min = min<arr[i]?min:arr[i];
    }

    int *help = new int[max+1];
    for (int i = 0; i < max+1; i++) {
        help[i] = 0;
    }

    //找出每个数字出现的次数
    for (int i = 0; i < n; i++) {
        int mapPos = arr[i] - min;
        help[mapPos]++;
    }

    int index = 0;
    for (int i = 0; i < max+1; i++) {
        while (help[i]-- > 0) {
            arr[index++] = i + min;
        }
    }
}


/**
 * 基数排序，通过数组记录对应的下标的数量。
 * @param arr
 * @param n
 */
void bucketSort(int  arr[], int n) {
    int max = -0x7fffffff;
    int min = 0x7fffffff;

    //找出数组中的最大最小值
    for (int i = 0; i < n; i++) {
        max = max>arr[i]?max:arr[i];
        min = min<arr[i]?min:arr[i];
    }

    vector<vector<int>> vector1;
    int bcounts = (max-min)/n+1;
    for(int i = 0;i<bcounts;i++){
        vector<int> v = vector<int>();
        vector1.push_back(v);
    }

    for(int i = 0;i<n;i++){
        int pos = (arr[i]-min)/n;
        vector1[pos].push_back(arr[i]);
    }

    int index = 0;
    for(int i = 0;i<bcounts;i++){
        sort(vector1[i].begin(),vector1[i].end());
        for(int x:vector1[i])
            arr[index++]=x;
    }

}
int main() {
    //计数排序测试
//    int n = 1000000;
//    cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
//    int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
//
//    TestSortHelper::testSort("count Sort Sort", countSort, arr1, n);
//    TestSortHelper::printArray(arr1,n);
//    countSort(arr1,n);
//    TestSortHelper::printArray(arr1,n);


//桶排序测试
    int n = 50;
    int range = 100;
    cout << "Test for Random Array, size = " << n << ", randome range [0, " << range << "]" << endl;
    int *arr1 = TestSortHelper::generateRandomArray(n, 0, range);

//    TestSortHelper::testSort("bucket Sort Sort", bucketSort, arr1, n);
    TestSortHelper::printArray(arr1,n);
    countSort(arr1,n);
    TestSortHelper::printArray(arr1,n);
    return 0;
}


